﻿// OptimizerPhase2.cpp

#include "OptimizerPhase2.h"
#include "Scoring.h"
#include "Validation.h"
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
#include <numeric>
#include <omp.h>
#include <limits>

OptimizationResult OptimizerPhase2::optimizer_systematic_search_bottleneck(
    const std::vector<int>& initial_schedule,
    const std::vector<long long>& initial_history,
    long long initial_score,
    const Graph& graph,
    const CodeMap& code_map,
    const Options2& options,
    std::mt19937& gen)
{
    std::vector<int> global_best_schedule = initial_schedule;
    long long global_best_score = initial_score;
    
    // 收敛历史记录
    std::vector<long long> convergence_history;
    std::vector<int> improvement_iterations;
    
    // 记录初始分数
    convergence_history.push_back(initial_score);
    improvement_iterations.push_back(0);

    auto total_start_time = std::chrono::high_resolution_clock::now();
    int num_nodes = graph.get_num_nodes();
    int num_cores = omp_get_max_threads();

    for (int ils_iter = 0; ils_iter <= options.num_perturbations; ++ils_iter) {
        auto current_time = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> elapsed = current_time - total_start_time;
        if (elapsed.count() > options.time_limit_minutes * 60) {
            fprintf(stdout, "  �׶ζ� > �Ѵﵽ %g ����ʱ�����ޣ���ֹILS������\n", options.time_limit_minutes);
            break;
        }

        std::vector<int> local_search_start_schedule;
        std::vector<long long> local_search_start_history;
        long long local_search_start_score;

        if (ils_iter == 0) {
            fprintf(stdout, "\n--- ��ʼ�״ζ�̬���� (Ѱ�ҵ�һ���ֲ����Ž�) ---\n");
            local_search_start_schedule = initial_schedule;
            local_search_start_history = initial_history;
            local_search_start_score = initial_score;
        }
        else {
            fprintf(stdout, "\n--- ��ʼ�� %d / %d ���Ŷ��������� ---\n", ils_iter, options.num_perturbations);

            const int MAX_PERTURB_ATTEMPTS = 100;
            bool perturbation_successful = false;
            std::vector<int> temp_schedule_perturbed;

            for (int attempt = 1; attempt <= MAX_PERTURB_ATTEMPTS; ++attempt) {
                int upper_b = std::max(3, static_cast<int>(floor(0.02 * num_nodes)));
                std::uniform_int_distribution<> moves_dist(3, upper_b);
                int num_moves = moves_dist(gen);

                std::vector<int> temp_schedule = global_best_schedule;
                for (int move_i = 0; move_i < num_moves; ++move_i) {
                    std::uniform_int_distribution<> node_dist(0, num_nodes - 1);
                    int node_to_move_idx_zero_based = node_dist(gen);
                    int node_to_move = temp_schedule[node_to_move_idx_zero_based];

                    std::vector<int> current_node_positions(num_nodes + 1, 0);
                    for (size_t i = 0; i < temp_schedule.size(); ++i) current_node_positions[temp_schedule[i]] = static_cast<int>(i + 1);

                    int latest_anc_pos = 0;
                    for (int parent_id : graph.get_predecessors(node_to_move)) {
                        latest_anc_pos = std::max(latest_anc_pos, current_node_positions[parent_id]);
                    }

                    int earliest_desc_pos = num_nodes + 1;
                    for (int child_id : graph.get_successors(node_to_move)) {
                        earliest_desc_pos = std::min(earliest_desc_pos, current_node_positions[child_id]);
                    }

                    std::vector<int> valid_range;
                    for (int i = latest_anc_pos + 1; i < earliest_desc_pos; ++i) {
                        if (i != node_to_move_idx_zero_based + 1) valid_range.push_back(i);
                    }

                    if (!valid_range.empty()) {
                        std::uniform_int_distribution<> pos_dist(0, (int)valid_range.size() - 1);
                        int new_pos_one_based = valid_range[pos_dist(gen)];

                        temp_schedule.erase(temp_schedule.begin() + node_to_move_idx_zero_based);
                        int adjusted_pos_zero_based = new_pos_one_based > node_to_move_idx_zero_based + 1 ? new_pos_one_based - 2 : new_pos_one_based - 1;
                        temp_schedule.insert(temp_schedule.begin() + adjusted_pos_zero_based, node_to_move);
                    }
                }

                if (Validation::is_l0_schedule_valid(temp_schedule, graph, code_map)) {
                    fprintf(stdout, "    > �ڵ� %d �γ����гɹ�������Ч�Ŷ��� (�ƶ�����: %d)��\n", attempt, num_moves);
                    temp_schedule_perturbed = temp_schedule;
                    perturbation_successful = true;
                    break;
                }
            }

            if (!perturbation_successful) {
                fprintf(stderr, "    > ����: ��%d�γ��Ժ�δ��������Ч���Ŷ��⣬��������ILS��\n", MAX_PERTURB_ATTEMPTS);
                continue;
            }

            local_search_start_schedule = temp_schedule_perturbed;
            auto score_hist = Scoring::calculate_max_vstay(local_search_start_schedule, graph, code_map);
            local_search_start_score = score_hist.first;
            local_search_start_history = score_hist.second;
        }

        std::vector<int> current_pass_schedule = local_search_start_schedule;
        long long current_pass_score = local_search_start_score;
        std::vector<long long> current_pass_history = local_search_start_history;

        for (int pass_num = 1; pass_num <= options.max_passes; ++pass_num) {
            fprintf(stdout, "  > Pass %d (��ǰ����: %lld)\n", pass_num, current_pass_score);
            bool improvement_found_in_pass = false;

            std::vector<int> node_positions(num_nodes + 1, 0);
            for (size_t i = 0; i < current_pass_schedule.size(); ++i) node_positions[current_pass_schedule[i]] = static_cast<int>(i) + 1;

            std::vector<int> latest_ancestor_pos(num_nodes + 1, 0);
            std::vector<int> earliest_descendant_pos(num_nodes + 1, num_nodes + 1);
            for (int n = 1; n <= num_nodes; ++n) {
                for (int parent_id : graph.get_predecessors(n)) {
                    latest_ancestor_pos[n] = std::max(latest_ancestor_pos[n], node_positions[parent_id]);
                }
                for (int child_id : graph.get_successors(n)) {
                    earliest_descendant_pos[n] = std::min(earliest_descendant_pos[n], node_positions[child_id]);
                }
            }

            auto max_it = std::max_element(current_pass_history.begin(), current_pass_history.end());
            int peak_idx = (int)std::distance(current_pass_history.begin(), max_it);
            if (current_pass_history.empty() || *max_it == 0) peak_idx = num_nodes - 1;

            std::vector<int> all_focus_nodes;
            for (int i = 0; i <= peak_idx; ++i) all_focus_nodes.push_back(current_pass_schedule[i]);
            std::shuffle(all_focus_nodes.begin(), all_focus_nodes.end(), gen);

            int focus_node_batch_size = options.num_focus_nodes_multiplier * num_cores;
            for (int focus_batch_start = 0; focus_batch_start < all_focus_nodes.size(); focus_batch_start += focus_node_batch_size) {
                int focus_batch_end = std::min(focus_batch_start + focus_node_batch_size, (int)all_focus_nodes.size());
                std::vector<int> current_focus_nodes_batch(all_focus_nodes.begin() + focus_batch_start, all_focus_nodes.begin() + focus_batch_end);

                std::vector<std::pair<int, int>> candidate_pool;
                for (int node_A : current_focus_nodes_batch) {
                    int win_start = latest_ancestor_pos[node_A] + 1;
                    int win_end = earliest_descendant_pos[node_A] - 1;
                    int current_pos_A = node_positions[node_A];
                    for (int p = win_start; p <= win_end; ++p) {
                        if (p != current_pos_A) candidate_pool.push_back({ node_A, p });
                    }
                }

                if (candidate_pool.empty()) continue;
                std::shuffle(candidate_pool.begin(), candidate_pool.end(), gen);

                int eval_batch_size = options.batch_size_multiplier * num_cores;
                for (int batch_start = 0; batch_start < candidate_pool.size(); batch_start += eval_batch_size) {
                    int batch_end = std::min(batch_start + eval_batch_size, (int)candidate_pool.size());

                    long long best_batch_score = std::numeric_limits<long long>::max();
                    std::vector<int> best_batch_schedule;

#pragma omp parallel
                    {
                        long long local_best_score = std::numeric_limits<long long>::max();
                        std::vector<int> local_best_schedule;
#pragma omp for
                        for (int k = batch_start; k < batch_end; ++k) {
                            int node_to_move_eval = candidate_pool[k].first;
                            int new_pos_eval = candidate_pool[k].second;
                            int original_pos_eval = node_positions[node_to_move_eval];

                            std::vector<int> temp_schedule = current_pass_schedule;
                            temp_schedule.erase(temp_schedule.begin() + original_pos_eval - 1);
                            int adjusted_pos = new_pos_eval > original_pos_eval ? new_pos_eval - 2 : new_pos_eval - 1;
                            temp_schedule.insert(temp_schedule.begin() + adjusted_pos, node_to_move_eval);

                            if (Validation::is_l0_schedule_valid(temp_schedule, graph, code_map)) {
                                long long score = Scoring::calculate_max_vstay(temp_schedule, graph, code_map).first;
                                if (score < local_best_score) {
                                    local_best_score = score;
                                    local_best_schedule = temp_schedule;
                                }
                            }
                        }
#pragma omp critical
                        {
                            if (local_best_score < best_batch_score) {
                                best_batch_score = local_best_score;
                                best_batch_schedule = local_best_schedule;
                            }
                        }
                    }

                    if (best_batch_score < current_pass_score) {
                        fprintf(stdout, "    > Pass %d - ���ָ����ƶ�, ������ %lld -> %lld\n", pass_num, current_pass_score, best_batch_score);
                        current_pass_score = best_batch_score;
                        current_pass_schedule = best_batch_schedule;
                        current_pass_history = Scoring::calculate_max_vstay(current_pass_schedule, graph, code_map).second;
                        improvement_found_in_pass = true;
                        break;
                    }
                }
                if (improvement_found_in_pass) break;
            }

            if (!improvement_found_in_pass) {
                fprintf(stdout, "  > Pass %d δ�����κθĽ�����̬����ģ�������\n", pass_num);
                break;
            }
        }

        if (current_pass_score < global_best_score) {
            fprintf(stdout, "--- 发现新的全局最优解！分数从 %lld 降低为 %lld ---\n", global_best_score, current_pass_score);
            global_best_score = current_pass_score;
            global_best_schedule = current_pass_schedule;
            
            // 记录收敛历史 (阶段2中，用ils_iter作为迭代标识)
            convergence_history.push_back(global_best_score);
            improvement_iterations.push_back(ils_iter + 1);  // ils_iter从0开始，所以+1
        }
        else {
            fprintf(stdout, "--- ��������δ��Խȫ�����Ž� (%lld vs %lld) ---\n", current_pass_score, global_best_score);
        }
    }

    // 返回优化结果和收敛历史
    OptimizationResult result;
    result.schedule = global_best_schedule;
    result.best_score = global_best_score;
    result.convergence_history = convergence_history;
    result.improvement_iterations = improvement_iterations;
    
    return result;
}